package com.dzu.easy;

import java.util.*;

/**
 * @author ZhaoDong
 * @date 2022/8/24 10:16
 * @description 1002. 查找共用字符
 * <p>
 * 给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（ 包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：words = ["bella","label","roller"]
 * 输出：["e","l","l"]
 * 示例 2：
 * <p>
 * 输入：words = ["cool","lock","cook"]
 * 输出：["c","o"]
 *  
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-common-characters
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test1002 {
    public static void main(String[] args) {
        List<String> list = commonChars(new String[]{"acabcddd", "bcbdbcbd", "baddbadb", "cbdddcac", "aacbcccd", "ccccddda", "cababaab", "addcaccd"});
        System.out.println(list);

    }

    // 4ms  71.47%
    public static List<String> commonChars4(String[] A) {
        //先得到第一个字符串里面每个字符的情况
        int[] charCount = new int[26];
        for (int i = 0; i < A[0].length(); i++) {
            charCount[A[0].charAt(i) - 'a']++;
        }

        //从第1个开始逐个进行比较
        for (int i = 1; i < A.length; i++) {
            int[] curCount = new int[26];

            //遍历第i个字符串
            for (int j = 0; j < A[i].length(); j++) {
                curCount[A[i].charAt(j) - 'a']++;
            }

            //将此时关于第i个字符串的情况与charCount对比，取小的即可
            for (int k = 0; k < 26; k++) {
                charCount[k] = Math.min(charCount[k], curCount[k]);
            }
        }

        //此时的charCount即为所有的字符串出现的共有的最小元素的个数
        List<String> result = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            while (charCount[i] != 0) {
                result.add(String.valueOf((char) (i + 'a')));
                charCount[i]--;
            }
        }

        return result;

    }

    // 16ms 7.22%
    public static List<String> commonChars(String[] words) {

        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < words[0].length(); i++) {
            char str = words[0].charAt(i);
            map.put(str, map.getOrDefault(str, 0) + 1);
        }

        for (String word : words) {
            HashMap<Character, Integer> temp = new HashMap<>();
            for (int i = 0; i < word.length(); i++) {
                char str = word.charAt(i);
                temp.put(str, temp.getOrDefault(str, 0) + 1);
            }
            Iterator<Map.Entry<Character, Integer>> iterator = map.entrySet().iterator();
            while (iterator.hasNext()) {
                Map.Entry<Character, Integer> entry = iterator.next();
                Character key = entry.getKey();
                Integer value = entry.getValue();
                Integer integer = temp.get(key);
                if (integer == null) {
                    iterator.remove();
                } else {
                    map.put(key, Math.min(value, integer));
                }
            }

        }
        List<String> list = new ArrayList<>();
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            Character key = entry.getKey();
            Integer value = entry.getValue();
            for (; value > 0; value--) {
                list.add(key.toString());
            }
        }

        return list;
    }
}
